home *** CD-ROM | disk | FTP | other *** search
/ Aminet 33 / Aminet 33 - October 1999.iso / Aminet / dev / c / GAPLib.lha / GAPLib / doc / text / Introduction < prev    next >
Encoding:
Text File  |  1999-04-23  |  2.2 KB  |  77 lines
  1.  
  2. A Short Introduction to Genetic Algorithms
  3.  
  4. Genetic algorithms are a class of fairly recent and remarkably
  5. powerful and flexible set of optimization/search strategies.
  6.  
  7. Genetic algorithms can be used for a multitude of problems such
  8. as function optimization, searching for solutions, best-fit problems,
  9. evolving rule-based control systems and much, much more.
  10.  
  11. The basic idea of genetic algorithms is the population. A set
  12. of candidate solutions or partial solutions which can
  13. be evaluated and compared to the other candidates in the set.
  14.  
  15. Historically, the most common type of representation for
  16. genetic algorithms has been the bitstring. So, if for no other
  17. reason than this, this mini introduction will only consider bitstrings.
  18.  
  19.  
  20. A general genetic algorith can be described quite simply like this:
  21.  
  22.  
  23. Let P be a set of candidate solutions to a problem such that each
  24. candidate solution can be directly or indirectly evaluated and
  25. assigned a fitness according to how good it is.
  26.  
  27. Pick candidates from P in such a manner that candidates with higher
  28. fitness have a higher probability of being selected. Generate a new
  29. individual from those picked by using crossover and mutation (explained
  30. below) and repeat until |P| new candidates have been generated.
  31. (|P| = the number of elements in P)
  32.  
  33. Form the set P' containing those individuals generated above.
  34.  
  35. Repeat until some criteria for stopping has been fulfilled. 
  36.  
  37.  
  38.  
  39. Crossover and mutation for bitstrings.
  40.  
  41.  
  42. Consider the two bitstrings 1110100011 and 0101011101, the common crossover
  43. operation for bistrings is simply a split-and-recombine operation. Let
  44. this example illustrate:
  45.  
  46. Example:
  47.  
  48. Perform crossover of the above bitstrings a position 3 counted from the right
  49. and beginning at zero.
  50.  
  51.       ---> Crossover point.
  52.       |
  53. 1110100011    Old bitstrings
  54. 0101011101
  55. ----------x
  56. 1110101101    New bitstrings
  57. 0101010011
  58.       ||||
  59.       --------> These bits have now been swapped between the bitstrings.
  60.  
  61. Multipoint crossover is the same thing but with several crossover points,
  62. this can be simulated by repeated singlepoint crossover.
  63.  
  64.  
  65. Mutation is simple the random flipping of one or more bits.
  66.  
  67. Example:
  68.  
  69. 1010000010
  70. ----------m
  71. 1110000010
  72.  |
  73.  ---- Mutated bit.
  74.  
  75.  
  76. The main idea is that 'good' sequences will stay in each 
  77.